#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

// 磁盘访问序列自增id
int work_id_inc = 1;
// 制作磁盘访问表格
vector<pair<int, int>> track_dist; // {io_req_no, track_dist} 
// define program 
struct Work{
  int id, ht, trackId; //磁盘id, 到达时间，访问磁道id，
  int st, ed; // start time, end time
  int need; // 读写花费时间 5~10， 每个磁道读写时间一致
  int acces_time; // 开始时间 
  int seek_dist; // 寻道距离
  int read_time, seek_time; // 读写时间， 寻道时间 
  bool in_wait, is_ok, working; // progress status
  friend ostream & operator << (ostream &out,const Work &w) {
	  out << w.id << " " << w.ht << " " << w.trackId << " " << w.need << endl;
    return out; }
  bool operator < (const Work &w)const {
    return ht < w.ht;
  }
  bool operator == (Work* w)const {
    return id < w->id;
  }
};
struct WorkResult{
  int id, w, ht; //进程id, 优先级, 到达时间
  int ed, tl, rw, cpt; // 结束时间，使用的时间片数量，就绪等待时间， CPU 占用时间 
  int iow, iot, turn, turn_w; // IO等待时间， IO占用时间，周转时间， 带权周转时间
  vector<pair<int, int>> jobs; // 片段序列 first is type { cpu | io { 1 | 2, second is time { 200
  friend ostream & operator << (ostream &out, const WorkResult &w){
	  out << " " << " " << w.id << " " << w.w << " " << w.ht << " " << w.ed << " " << w.tl << " " << w.rw << " " << w.cpt << " " << w.iow << " " << w.iot << endl;
	  return out;
  }
};

// sstf 需要一个等待队列
vector<Work*> qwait;
void datacreate(int n){
  if ( n < 10 && n > 100) {
    cout << "磁盘访问数量需要在10 ～ 100 之间" << endl;
    exit(1);
  }
  fstream f ("job", ios::out);
  vector<Work> jobs;
  f << n << endl;
  for (int i = 0; i < n; i++){
    Work w = {.id=work_id_inc++,.ht = rand() % 200, .trackId = rand() % 200, .need = rand() % 6 + 5};
    jobs.push_back(w);
  }
  sort(jobs.begin(), jobs.end());
  for (auto x: jobs){
    f << x;
  }
  f.close();
}

void init(int n){
  datacreate(n);
}
vector<Work*> jobs;
// 读取数据
void input(){
	fstream f("job", ios::in);
	int n;
	f >> n;
	while (n--) {
		Work * t = new Work{};
		f >> t->id >> t->ht >> t->trackId >> t->need;
		jobs.push_back(t);
	}
}
// 初始磁头位置
int dist_pointer = 143;
// req_no 磁道位置
int FCFS(const int req_no,Work* const w){
	int dist = 0;
	dist = abs(dist_pointer - req_no);
	track_dist.push_back({req_no, dist});
	w->seek_dist = dist;
	dist_pointer = req_no;
	w->is_ok = true;
	return dist * 2;
}
// req_no 没有意义
int SSTF(const int _req_no,Work* const w, int time){
	int min = 0x3f3f3f3f;
	Work* t = nullptr;
	for (auto x: qwait){
		if (x->is_ok) continue;
		int dist = abs(dist_pointer - x->trackId);
		if (min > dist){ min = dist; t = x; }
	}
	if (t == nullptr){
		cout << " 程序出现错误" << endl;
		exit(1);
	}

    // cout << " 正在处理" << t->id << endl;
	dist_pointer = t->trackId;
	t->st = time;
	t->seek_dist = min;
	t->is_ok = true;
	track_dist.push_back({t->trackId, min});
	return min * 2;
}
// req_no 没有意义
int EA(const int _req_no,Work* const w, const int tracK_len, int time){
	int min = 0x3f3f3f3f, max = 0;
	Work* t = nullptr;
	for (auto x: qwait){ if (x->is_ok) continue; max = std::max(max, x->trackId);}
	bool walkUp = dist_pointer < max; // 能网上走我就，往上走
	for (auto x: qwait){
		if (x->is_ok) continue;
		// cout << (walkUp && x->trackId < dist_pointer) << " ";
		if (walkUp && x->trackId < dist_pointer) continue;
		int dist = abs(dist_pointer - x->trackId);
		if (min > dist){ min = dist; t = x; }
	}
	cout << endl;
	if (t == nullptr){
		cout << " 程序出现错误" << endl;
		exit(1);
	}
    cout << " 正在处理" << t->id << endl;
	dist_pointer = t->trackId;
	t->is_ok = true;
	t->st = time;
	t->seek_dist = min;
	track_dist.push_back({t->trackId, min});
	return min * 2;
}
// type
int handle_disk_req(const int _req_no,Work* const w, const int tracK_len, int time, const int type){
	switch (type) {
		case 1:{return FCFS(_req_no, w);}
		case 2:{return SSTF(0, nullptr, time);}
		case 3:{return EA(0, nullptr, tracK_len, time);}
		default: {return 1; break;}
	}
}

bool cpu = false;

int main (int argc, char *argv[])
{
  //init(10);
  input();
  Work * cpuworkingWork = nullptr;
  for (int i = 0 ; i < 1999; i++){
	  if (cpu && cpuworkingWork != nullptr){
		  // 磁头移动消耗的时间
		  // cout << " 正在处理" << cpuworkingWork->id << endl; // FCFS 有效果
		  for (auto x: qwait) {cout << x->id << " "; } cout << endl;
		  int trackNeed = handle_disk_req(cpuworkingWork->trackId, cpuworkingWork, i, 200, 2);
		  // 读写耗费时间
		  i += trackNeed + cpuworkingWork->need;
		  cpuworkingWork->ed = i;
		  cpu = false;
		  cpuworkingWork = nullptr;
	  }

	  for (auto x: jobs){
		  if (x->in_wait) continue;
		  if (x->ht <= i) { 
			  x->in_wait = true;
			  qwait.push_back(x);
		  }
	  }
	  if (!cpu && cpuworkingWork == nullptr){
		  for (auto x: qwait){
			  if (x->is_ok) continue;
			  if (cpu) continue;
			  cpuworkingWork = x;
			  cpu = true;
		  }
	  }
  }
  // 写入文件
  fstream f("disks", ios::out);
  cout << jobs.size() << endl;
  for (auto x: jobs){
	  f << x->id << " " << x->ht << " " << x->ed << " " << x->trackId << " " << x->seek_dist << " " << x->need << " " << x->st << " " << endl;
  }

  for (auto x: track_dist){
	  cout << x.first << "\t";
  }
  int sum = 0;
  cout << endl;
  for (auto x: track_dist){
	  sum += x.second;
	  cout << x.second << "\t";
  }
  cout << endl;
  cout << sum << "\t " << double(sum) / track_dist.size() << "\t ";

  return 0;
}
